home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Borland / Borland C++ V5.02 / INC.PAK / TREE.H < prev    next >
C/C++ Source or Header  |  1997-05-06  |  40KB  |  1,257 lines
  1. #ifndef __STD_TREE__
  2. #define __STD_TREE__
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * tree - Declarations for the Standard Library tree classes
  8.  *
  9.  * $Id: tree,v 1.43 1995/09/18 23:41:41 lijewski Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED
  29.  *
  30.  * The software and information contained herein are proprietary to, and
  31.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  32.  * intends to preserve as trade secrets such software and information.
  33.  * This software is furnished pursuant to a written license agreement and
  34.  * may be used, copied, transmitted, and stored only in accordance with
  35.  * the terms of such license and with the inclusion of the above copyright
  36.  * notice.  This software and information or any other copies thereof may
  37.  * not be provided or otherwise made available to any other person.
  38.  *
  39.  * Notwithstanding any other lease or license that may pertain to, or
  40.  * accompany the delivery of, this computer software and information, the
  41.  * rights of the Government regarding its use, reproduction and disclosure
  42.  * are as set forth in Section 52.227-19 of the FARS Computer
  43.  * Software-Restricted Rights clause.
  44.  *
  45.  * Use, duplication, or disclosure by the Government is subject to
  46.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  47.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  48.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  49.  * P.O. Box 2328, Corvallis, Oregon 97339.
  50.  *
  51.  * This computer software and information is distributed with "restricted
  52.  * rights."  Use, duplication or disclosure is subject to restrictions as
  53.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  54.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  55.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  56.  * then the "Alternate III" clause applies.
  57.  *
  58.  **************************************************************************/
  59.  
  60. /*
  61. **
  62. ** Red-black tree class, designed for use in implementing STL
  63. ** associative containers (set, multiset, map, and multimap). The
  64. ** insertion and deletion algorithms are based on those in Cormen,
  65. ** Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
  66. ** except that:
  67. **
  68. ** (1) the header cell is maintained with links not only to the root
  69. ** but also to the leftmost node of the tree, to enable constant time
  70. ** begin(), and to the rightmost node of the tree, to enable linear time
  71. ** performance when used with the generic set algorithms (set_union,
  72. ** etc.);
  73. **
  74. ** (2) when a node being deleted has two children its successor node is
  75. ** relinked into its place, rather than copied, so that the only
  76. ** iterators invalidated are those referring to the deleted node.
  77. **
  78. */
  79.  
  80. #include <stdcomp.h>
  81.  
  82. #include <algorith>
  83. #include <iterator>
  84. #include <function>
  85.  
  86. #ifdef RWSTD_MULTI_THREAD
  87. #include <stdmutex.h>
  88. #endif
  89.  
  90. #ifndef RWSTD_NO_NAMESPACE
  91. namespace std {
  92. #endif
  93.  
  94. #ifndef rb_tree
  95. #define rb_tree rb_tree
  96. #endif
  97.  
  98.  
  99. //
  100. // And a mutex to ensure NIL gets set properly for each type of tree.
  101. //
  102. #ifdef RWSTD_MULTI_THREAD
  103. extern RWSTDMutex __stl_tree_mutex;
  104. #endif
  105.  
  106. template <class Key, class Value, class KeyOfValue, class Compare>
  107. class rb_tree
  108. {
  109.   protected:
  110.  
  111.     enum color_type { RED, BLACK };
  112.     typedef Allocator<void>::pointer void_pointer;
  113.  
  114.     struct rb_tree_node;
  115.     friend struct rb_tree_node;
  116.  
  117.     struct rb_tree_node
  118.     {
  119.         color_type   color_field;
  120.         void_pointer parent_link;
  121.         void_pointer left_link;
  122.         void_pointer right_link;
  123.         Value        value_field;
  124.     };
  125.  
  126.     Allocator<rb_tree_node> rb_tree_node_allocator;
  127.     Allocator<Value>        value_allocator;
  128.  
  129.   public:
  130.  
  131.     typedef Key                                      key_type;
  132.     typedef Value                                    value_type;
  133.     typedef Allocator<Value>::pointer                pointer;
  134.     typedef Allocator<Value>::reference              reference;
  135.     typedef Allocator<Value>::const_reference        const_reference;
  136.     typedef Allocator<rb_tree_node>                  rb_tree_node_allocator_type;
  137.     typedef Allocator<rb_tree_node>::pointer         link_type;
  138.     typedef Allocator<rb_tree_node>::size_type       size_type;
  139.     typedef Allocator<rb_tree_node>::difference_type difference_type;
  140.  
  141.   protected:
  142.  
  143.     static size_type buffer_size ()
  144.     {
  145.         //
  146.         // Each time we allocate memory for nodes we reserve space for
  147.         // a chunk of rb_tree_nodes.  This is currently tuned to
  148.         // allocate memory in 1K chunks, except for very large nodes.
  149.         //
  150.         return sizeof(rb_tree_node) >= 1024 ? 1 : 1024 / sizeof(rb_tree_node);
  151.     }
  152.  
  153.     struct rb_tree_node_buffer;
  154.     friend struct rb_tree_node_buffer;
  155.  
  156.     struct rb_tree_node_buffer
  157.     {
  158.         void_pointer next_buffer;
  159.         link_type buffer;
  160.     };
  161.  
  162.   public:
  163.  
  164.     typedef Allocator<rb_tree_node_buffer>          buffer_allocator_type;
  165.     typedef Allocator<rb_tree_node_buffer>::pointer buffer_pointer;
  166.  
  167.   protected:
  168.  
  169.     Allocator<rb_tree_node_buffer> buffer_allocator;
  170.     buffer_pointer                 buffer_list;
  171.     link_type                      free_list;
  172.     link_type                      next_avail;
  173.     link_type                      last;
  174.  
  175.     void add_new_buffer ()
  176.     {
  177.         buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
  178.         tmp->buffer        = rb_tree_node_allocator.allocate(buffer_size());
  179.         tmp->next_buffer   = buffer_list;
  180.         buffer_list        = tmp;
  181.         next_avail         = buffer_list->buffer;
  182.         last               = next_avail + buffer_size();
  183.     }
  184.     void deallocate_buffers ();
  185.     link_type get_node ()
  186.     {
  187.         link_type tmp = free_list;
  188.         return free_list ?
  189.             (free_list = (link_type)(free_list->right_link), tmp)
  190.                 : (next_avail == last ? (add_new_buffer(), next_avail++)
  191.                    : next_avail++);
  192.     }
  193.     void put_node (link_type p) { p->right_link = free_list; free_list = p; }
  194.  
  195.   protected:
  196.  
  197.     link_type  header;
  198.     link_type& root      ()       { return parent(header); }
  199.     link_type& root      () const { return parent(header); }
  200.     link_type& leftmost  ()       { return left(header);   }
  201.     link_type& leftmost  () const { return left(header);   }
  202.     link_type& rightmost ()       { return right(header);  }
  203.     link_type& rightmost () const { return right(header);  }
  204.  
  205.     size_type  node_count;    // Keeps track of size of tree.
  206.     bool       insert_always; // Controls whether an element already in the
  207.                               // tree is inserted again.
  208.     Compare   key_compare;
  209.  
  210.     static link_type NIL;
  211.     static size_type number_of_trees;
  212.  
  213.     static link_type& left (link_type x)
  214.     {
  215.         return (link_type&)((*x).left_link);
  216.     }
  217.     static link_type& right (link_type x)
  218.     {
  219.         return (link_type&)((*x).right_link);
  220.     }
  221.     static link_type& parent (link_type x)
  222.     {
  223.         return (link_type&)((*x).parent_link);
  224.     }
  225.     static reference value (link_type x) { return (*x).value_field; }
  226.     static Allocator<Key>::const_reference key (link_type x)
  227.     {
  228.         return KeyOfValue()(value(x));
  229.     }
  230.     static color_type& color (link_type x)
  231.     {
  232.         return (color_type&)(*x).color_field;
  233.     }
  234.     static link_type minimum (link_type x)
  235.     {
  236.         while (left(x) != NIL) x = left(x);
  237.         return x;
  238.     }
  239.     static link_type maximum (link_type x)
  240.     {
  241.         while (right(x) != NIL) x = right(x);
  242.         return x;
  243.     }
  244.  
  245.   public:
  246.  
  247.     class  iterator;
  248.     friend class iterator;
  249.     class  const_iterator;
  250.     friend class const_iterator;
  251.  
  252.     class iterator : public bidirectional_iterator<Value, difference_type>
  253.     {
  254.         friend class rb_tree<Key, Value, KeyOfValue, Compare>;
  255.         friend class const_iterator;
  256.  
  257.       protected:
  258.  
  259.         link_type node;
  260.         iterator (link_type x) : node(x) {}
  261.  
  262.       public:
  263.  
  264.         iterator () {}
  265.         bool operator== (const iterator& y) const { return node == y.node; }
  266.         reference operator* () const { return value(node); }
  267.         iterator& operator++ ()
  268.         {
  269.             if (right(node) != NIL)
  270.             {
  271.                 node = right(node);
  272.                 while (left(node) != NIL) node = left(node);
  273.             }
  274.             else
  275.             {
  276.                 link_type y = parent(node);
  277.                 while (node == right(y))
  278.                 {
  279.                     node = y; y = parent(y);
  280.                 }
  281.                 if (right(node) != y) // Necessary because of rightmost.
  282.                     node = y;
  283.             }
  284.             return *this;
  285.         }
  286.         iterator operator++ (int)
  287.         {
  288.             iterator tmp = *this; ++*this; return tmp;
  289.         }
  290.         iterator& operator-- ()
  291.         {
  292.             if (color(node) == RED && parent(parent(node)) == node)
  293.                 //
  294.                 // Check for header.
  295.                 //
  296.                 node = right(node);   // Return rightmost.
  297.             else if (left(node) != NIL)
  298.             {
  299.                 link_type y = left(node);
  300.                 while (right(y) != NIL) y = right(y);
  301.                 node = y;
  302.             }
  303.             else
  304.             {
  305.                 link_type y = parent(node);
  306.                 while (node == left(y))
  307.                 {
  308.                     node = y; y = parent(y);
  309.                 }
  310.                 node = y;
  311.             }
  312.             return *this;
  313.         }
  314.         iterator operator-- (int)
  315.         {
  316.             iterator tmp = *this; --*this; return tmp;
  317.         }
  318.     };  // End of definition of iterator.
  319.  
  320.     class const_iterator
  321.         : public bidirectional_iterator<Value,difference_type>
  322.     {
  323.         friend class rb_tree<Key, Value, KeyOfValue, Compare>;
  324.         friend class iterator;
  325.  
  326.       protected:
  327.  
  328.         link_type node;
  329.         const_iterator (link_type x) : node(x) {}
  330.  
  331.       public:
  332.  
  333.         const_iterator () {}
  334.         const_iterator (const iterator& x) : node(x.node) {}
  335.         bool operator== (const const_iterator& y) const
  336.         {
  337.             return node == y.node;
  338.         }
  339.         bool operator!= (const const_iterator& y) const
  340.         {
  341.             return node != y.node;
  342.         }
  343.         const_reference operator* () const { return value(node); }
  344.         const_iterator& operator++ ()
  345.         {
  346.             if (right(node) != NIL)
  347.             {
  348.                 node = right(node);
  349.                 while (left(node) != NIL) node = left(node);
  350.             }
  351.             else
  352.             {
  353.                 link_type y = parent(node);
  354.                 while (node == right(y))
  355.                 {
  356.                     node = y; y = parent(y);
  357.                 }
  358.                 if (right(node) != y) // Necessary because of rightmost.
  359.                     node = y;
  360.             }
  361.             return *this;
  362.         }
  363.         const_iterator operator++ (int)
  364.         {
  365.             const_iterator tmp = *this; ++*this; return tmp;
  366.         }
  367.         const_iterator& operator-- ()
  368.         {
  369.             if (color(node) == RED && parent(parent(node)) == node)
  370.                 //
  371.                 // Check for header.
  372.                 //
  373.                 node = right(node);   // return rightmost
  374.             else if (left(node) != NIL)
  375.             {
  376.                 link_type y = left(node);
  377.                 while (right(y) != NIL) y = right(y);
  378.                 node = y;
  379.             }
  380.             else
  381.             {
  382.                 link_type y = parent(node);
  383.                 while (node == left(y))
  384.                 {
  385.                     node = y; y = parent(y);
  386.                 }
  387.                 node = y;
  388.             }
  389.             return *this;
  390.         }
  391.         const_iterator operator-- (int)
  392.         {
  393.             const_iterator tmp = *this; --*this; return tmp;
  394.         }
  395.     };  // End of definition of const_iterator.
  396.  
  397.     typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  398.                                            difference_type>
  399.             reverse_iterator;
  400.     typedef reverse_bidirectional_iterator<const_iterator, value_type,
  401.                                            const_reference, difference_type>
  402.             const_reverse_iterator;
  403.  
  404.   private:
  405.  
  406.     iterator  __insert (link_type x, link_type y, const value_type& v);
  407.     link_type __copy   (link_type x, link_type p);
  408.     void      __erase  (link_type x);
  409.     void init ()
  410.     {
  411.         buffer_list = 0;
  412.         free_list = next_avail = last = 0;
  413.  
  414.         {
  415. #ifdef RWSTD_MULTI_THREAD
  416.             RWSTDGuard guard(__stl_tree_mutex);
  417. #endif
  418.             ++number_of_trees;
  419.  
  420.             if (NIL == 0)
  421.             {
  422.                 NIL         = rb_tree_node_allocator.allocate((size_type)1);
  423.                 color(NIL)  = BLACK;
  424.                 parent(NIL) = 0;
  425.                 left(NIL)   = 0;
  426.                 right(NIL)  = 0;
  427.             }
  428.         }
  429.         header        = get_node();
  430.         color(header) = RED;  // Used to distinguish header from root
  431.                               // in iterator.operator++.
  432.         root()      = NIL;
  433.         leftmost()  = header;
  434.         rightmost() = header;
  435.     }
  436.   public:
  437.  
  438.     rb_tree (const Compare& comp = Compare(), bool always = true)
  439.            : node_count(0), key_compare(comp), insert_always(always)
  440.     {
  441.         init();
  442.     }
  443.  
  444. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  445.     template<class InputIterator>
  446.     rb_tree (InputIterator first, InputIterator last,
  447.              const Compare& comp = Compare(), bool always = true)
  448.           : node_count(0), key_compare(comp), insert_always(always)
  449.     {
  450.         init(); insert(first, last);
  451.     }
  452. #else
  453.     rb_tree (const value_type* first, const value_type* last,
  454.              const Compare& comp = Compare(), bool always = true)
  455.           : node_count(0), key_compare(comp), insert_always(always)
  456.     {
  457.         init(); insert(first, last);
  458.     }
  459.     rb_tree (const_iterator first, const_iterator last,
  460.              const Compare& comp = Compare(), bool always = true)
  461.           : node_count(0), key_compare(comp), insert_always(always)
  462.     {
  463.         init(); insert(first, last);
  464.     }
  465. #endif
  466.  
  467.     rb_tree (const rb_tree<Key,Value,KeyOfValue,Compare>& x, bool always = true)
  468.         : node_count(x.node_count), key_compare(x.key_compare),
  469.           insert_always(always)
  470.     {
  471.         {
  472. #ifdef RWSTD_MULTI_THREAD
  473.             RWSTDGuard guard(__stl_tree_mutex);
  474. #endif
  475.             ++number_of_trees;
  476.         }
  477.         buffer_list   = 0;
  478.         free_list     = next_avail = last = 0;
  479.         header        = get_node();
  480.         color(header) = RED;
  481.         root()        = __copy(x.root(), header);
  482.         if (root() == NIL)
  483.         {
  484.             leftmost() = header; rightmost() = header;
  485.         }
  486.         else
  487.         {
  488.             leftmost() = minimum(root()); rightmost() = maximum(root());
  489.         }
  490.     }
  491.     ~rb_tree ()
  492.      {
  493.         erase(begin(), end());
  494.         put_node(header);
  495.         deallocate_buffers();
  496.  
  497. #ifdef RWSTD_MULTI_THREAD
  498.         RWSTDGuard guard(__stl_tree_mutex);
  499. #endif
  500.         if (--number_of_trees == 0)
  501.         {
  502.             rb_tree_node_allocator.deallocate(NIL);
  503.             NIL = 0;
  504.         }
  505.     }
  506.     rb_tree<Key, Value, KeyOfValue, Compare>&
  507.         operator= (const rb_tree<Key, Value, KeyOfValue, Compare>& x);
  508.  
  509.     Compare     key_comp () const { return key_compare; }
  510.  
  511.     iterator       begin ()       { return leftmost(); }
  512.     const_iterator begin () const { return leftmost(); }
  513.     iterator       end   ()       { return header;     }
  514.     const_iterator end   () const { return header;     }
  515.  
  516.     reverse_iterator rbegin ()
  517.     {
  518.       reverse_iterator tmp(end()); return tmp;
  519.     }
  520.     const_reverse_iterator rbegin () const
  521.     {
  522.       const_reverse_iterator tmp(end()); return tmp;
  523.     }
  524.     reverse_iterator rend ()
  525.     {
  526.       reverse_iterator tmp(begin()); return tmp;
  527.     }
  528.     const_reverse_iterator rend () const
  529.     {
  530.       const_reverse_iterator tmp(begin()); return tmp;
  531.     }
  532.  
  533.     bool      empty    () const { return node_count == 0; }
  534.     size_type size     () const { return node_count;      }
  535.     size_type max_size () const
  536.     {
  537.         return rb_tree_node_allocator.max_size();
  538.     }
  539.     void swap (rb_tree<Key, Value, KeyOfValue, Compare>& t)
  540.     {
  541. #ifndef RWSTD_NO_NAMESPACE
  542.         std::swap(buffer_allocator, t.buffer_allocator);
  543.         std::swap(buffer_list, t.buffer_list);
  544.         std::swap(free_list, t.free_list);
  545.         std::swap(next_avail, t.next_avail);
  546.         std::swap(last, t.last);
  547.         std::swap(header, t.header);
  548.         std::swap(node_count, t.node_count);
  549.         std::swap(insert_always, t.insert_always);
  550.         std::swap(key_compare, t.key_compare);
  551.         std::swap(rb_tree_node_allocator, t.rb_tree_node_allocator);
  552.         std::swap(value_allocator, t.value_allocator);
  553. #else
  554.         ::swap(buffer_allocator, t.buffer_allocator);
  555.         ::swap(buffer_list, t.buffer_list);
  556.         ::swap(free_list, t.free_list);
  557.         ::swap(next_avail, t.next_avail);
  558.         ::swap(last, t.last);
  559.         ::swap(header, t.header);
  560.         ::swap(node_count, t.node_count);
  561.         ::swap(insert_always, t.insert_always);
  562.         ::swap(key_compare, t.key_compare);
  563.         ::swap(rb_tree_node_allocator, t.rb_tree_node_allocator);
  564.         ::swap(value_allocator, t.value_allocator);
  565. #endif
  566.     }
  567.  
  568.     typedef  pair<iterator, bool> pair_iterator_bool;
  569.     //
  570.     // typedef done to get around compiler bug.
  571.     //
  572.  
  573. #ifndef RWSTD_NO_RET_TEMPLATE
  574.     pair<iterator,bool> insert (const value_type& x);
  575. #else
  576.     pair_iterator_bool  insert (const value_type& x);
  577. #endif
  578.  
  579.     iterator  insert (iterator position, const value_type& x);
  580.  
  581. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  582. template<class Iterator>
  583.     void      insert (Iterator first, Iterator last);
  584. #else
  585.     void      insert (const_iterator first, const_iterator last);
  586.     void      insert (const value_type* first, const value_type* last);
  587. #endif
  588.  
  589.     void      erase  (iterator position);
  590.     size_type erase  (const key_type& x);
  591.     void      erase  (iterator first, iterator last);
  592.     void      erase  (const key_type* first, const key_type* last);
  593.  
  594.     iterator       find        (const key_type& x);
  595.     const_iterator find        (const key_type& x) const;
  596.     size_type      count       (const key_type& x) const;
  597.     iterator       lower_bound (const key_type& x);
  598.     const_iterator lower_bound (const key_type& x) const;
  599.     iterator       upper_bound (const key_type& x);
  600.     const_iterator upper_bound (const key_type& x) const;
  601.  
  602.     typedef  pair<iterator, iterator> pair_iterator_iterator;
  603.     //
  604.     // typedef done to get around compiler bug.
  605.     //
  606. #ifndef RWSTD_NO_RET_TEMPLATE
  607.     pair<iterator,iterator> equal_range (const key_type& x);
  608. #else
  609.     pair_iterator_iterator equal_range (const key_type& x);
  610. #endif
  611.  
  612.     typedef  pair<const_iterator, const_iterator> pair_citerator_citerator;
  613. #ifndef RWSTD_NO_RET_TEMPLATE
  614.     pair<const_iterator, const_iterator> equal_range (const key_type& x) const;
  615. #else
  616.     pair_citerator_citerator equal_range (const key_type& x) const;
  617. #endif
  618.     inline void rotate_left  (link_type x);
  619.     inline void rotate_right (link_type x);
  620. };
  621.  
  622. template <class Key, class Value, class KeyOfValue, class Compare>
  623. rb_tree<Key, Value, KeyOfValue, Compare>::link_type
  624. rb_tree<Key, Value, KeyOfValue, Compare>::NIL = 0;
  625.  
  626. template <class Key, class Value, class KeyOfValue, class Compare>
  627. rb_tree<Key, Value, KeyOfValue, Compare>::size_type
  628. rb_tree<Key, Value, KeyOfValue, Compare>::number_of_trees = 0;
  629.  
  630. template <class Key, class Value, class KeyOfValue, class Compare>
  631. void rb_tree<Key, Value, KeyOfValue, Compare>::deallocate_buffers ()
  632. {
  633.     while (buffer_list)
  634.     {
  635.         buffer_pointer tmp = buffer_list;
  636.         buffer_list        = (buffer_pointer)(buffer_list->next_buffer);
  637.         rb_tree_node_allocator.deallocate(tmp->buffer);
  638.         buffer_allocator.deallocate(tmp);
  639.     }
  640. }
  641.  
  642. template <class Key, class Value, class KeyOfValue, class Compare>
  643. inline bool operator== (const rb_tree<Key, Value, KeyOfValue, Compare>& x,
  644.                         const rb_tree<Key, Value, KeyOfValue, Compare>& y)
  645. {
  646.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  647. }
  648.  
  649. template <class Key, class Value, class KeyOfValue, class Compare>
  650. inline bool operator< (const rb_tree<Key, Value, KeyOfValue, Compare>& x,
  651.                        const rb_tree<Key, Value, KeyOfValue, Compare>& y)
  652. {
  653.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  654. }
  655.  
  656. template <class Key, class Value, class KeyOfValue, class Compare>
  657. rb_tree<Key, Value, KeyOfValue, Compare>&
  658. rb_tree<Key, Value, KeyOfValue, Compare>::
  659. operator= (const rb_tree<Key, Value, KeyOfValue, Compare>& x)
  660. {
  661.     if (!(this == &x))
  662.     {
  663.         //
  664.         // Can't be done as in list because Key may be a constant type.
  665.         //
  666.         erase(begin(), end());
  667.         root() = __copy(x.root(), header);
  668.         if (root() == NIL)
  669.         {
  670.             leftmost()  = header; rightmost() = header;
  671.         }
  672.         else
  673.         {
  674.             leftmost()  = minimum(root()); rightmost() = maximum(root());
  675.         }
  676.         node_count = x.node_count;
  677.     }
  678.     return *this;
  679. }
  680.  
  681. template <class Key, class Value, class KeyOfValue, class Compare>
  682. rb_tree<Key, Value, KeyOfValue, Compare>::iterator
  683. rb_tree<Key, Value, KeyOfValue, Compare>::
  684. __insert (link_type x, link_type y, const Value& v)
  685. {
  686.     ++node_count;
  687.     link_type z = get_node();
  688.     construct(value_allocator.address(value(z)), v);
  689.     if (y == header || x != NIL || key_compare(KeyOfValue()(v), key(y)))
  690.     {
  691.         left(y) = z;  // Also makes leftmost() = z when y == header.
  692.         if (y == header)
  693.         {
  694.             root() = z; rightmost() = z;
  695.         }
  696.         else if (y == leftmost())
  697.             leftmost() = z;   // Maintain leftmost() pointing to minimum node.
  698.     }
  699.     else
  700.     {
  701.         right(y) = z;
  702.         if (y == rightmost())
  703.             rightmost() = z;  // Maintain rightmost() pointing to maximum node.
  704.     }
  705.     parent(z) = y;
  706.     left(z) = NIL;
  707.     right(z) = NIL;
  708.     x = z;  // Recolor and rebalance the tree.
  709.     color(x) = RED;
  710.     while (x != root() && color(parent(x)) == RED)
  711.         if (parent(x) == left(parent(parent(x))))
  712.         {
  713.             y = right(parent(parent(x)));
  714.             if (color(y) == RED)
  715.             {
  716.                 color(parent(x))         = BLACK;
  717.                 color(y)                 = BLACK;
  718.                 color(parent(parent(x))) = RED;
  719.                 x                        = parent(parent(x));
  720.             }
  721.             else
  722.             {
  723.                 if (x == right(parent(x)))
  724.                 {
  725.                     x = parent(x); rotate_left(x);
  726.                 }
  727.                 color(parent(x)) = BLACK;
  728.                 color(parent(parent(x))) = RED;
  729.                 rotate_right(parent(parent(x)));
  730.             }
  731.         }
  732.         else
  733.         {
  734.             y = left(parent(parent(x)));
  735.             if (color(y) == RED)
  736.             {
  737.                 color(parent(x))         = BLACK;
  738.                 color(y)                 = BLACK;
  739.                 color(parent(parent(x))) = RED;
  740.                 x                        = parent(parent(x));
  741.             }
  742.             else
  743.             {
  744.                 if (x == left(parent(x)))
  745.                 {
  746.                     x = parent(x); rotate_right(x);
  747.                 }
  748.                 color(parent(x))         = BLACK;
  749.                 color(parent(parent(x))) = RED;
  750.                 rotate_left(parent(parent(x)));
  751.             }
  752.         }
  753.     color(root()) = BLACK;
  754.     return iterator(z);
  755. }
  756.  
  757. template <class Key, class Value, class KeyOfValue, class Compare>
  758. rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool
  759. rb_tree<Key, Value, KeyOfValue, Compare>::insert (const Value& v)
  760. {
  761.     link_type y = header;
  762.     link_type x = root();
  763.     bool comp   = true;
  764.     while (x != NIL)
  765.     {
  766.         y    = x;
  767.         comp = key_compare(KeyOfValue()(v), key(x));
  768.         x    = comp ? left(x) : right(x);
  769.     }
  770.     if (insert_always)
  771.     {
  772.         pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  773.     }
  774.     iterator j = iterator(y);
  775.     if (comp)
  776.         if (j == begin())
  777.         {
  778.             pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  779.         }
  780.         else
  781.             --j;
  782.     if (key_compare(key(j.node), KeyOfValue()(v)))
  783.     {
  784.         pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  785.     }
  786.     pair_iterator_bool tmp(j, false);
  787.     return tmp;
  788. }
  789.  
  790. template <class Key, class Value, class KeyOfValue, class Compare>
  791. rb_tree<Key, Value, KeyOfValue, Compare>::iterator
  792. rb_tree<Key, Value, KeyOfValue, Compare>::insert (iterator position,
  793.                                                   const Value& v)
  794. {
  795.     if (position == iterator(begin()))
  796.         if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
  797.             return __insert(position.node, position.node, v);
  798.             //
  799.             // First argument just needs to be non-NIL.
  800.             //
  801.         else
  802.             return insert(v).first;
  803.     else if (position == iterator(end()))
  804.         if (key_compare(key(rightmost()), KeyOfValue()(v)))
  805.             return __insert(NIL, rightmost(), v);
  806.         else
  807.             return insert(v).first;
  808.     else
  809.     {
  810.         iterator before = --position;
  811.         if (key_compare(key(before.node), KeyOfValue()(v))
  812.             && key_compare(KeyOfValue()(v), key(position.node)))
  813.             if (right(before.node) == NIL)
  814.                 return __insert(NIL, before.node, v);
  815.             else
  816.                 return __insert(position.node, position.node, v);
  817.                 //
  818.                 // First argument just needs to be non-NIL.
  819.                 //
  820.         else
  821.             return insert(v).first;
  822.     }
  823. }
  824.  
  825. #ifndef RWSTD_NO_MEMBER_TEMPLATES
  826. template <class Key, class Value, class KeyOfValue, class Compare>
  827. template<class Iterator>
  828. void rb_tree<Key, Value, KeyOfValue, Compare>::insert (Iterator first,
  829.                                                        Iterator last)
  830. {
  831.     while (first != last) insert(*first++);
  832. }
  833. #else
  834. template <class Key, class Value, class KeyOfValue, class Compare>
  835. void rb_tree<Key, Value, KeyOfValue, Compare>::insert (const_iterator first,
  836.                                                        const_iterator last)
  837. {
  838.     while (first != last) insert(*first++);
  839. }
  840.  
  841. template <class Key, class Value, class KeyOfValue, class Compare>
  842. void rb_tree<Key, Value, KeyOfValue, Compare>::insert (const Value* first,
  843.                                                        const Value* last)
  844. {
  845.     while (first != last) insert(*first++);
  846. }
  847. #endif
  848.  
  849. template <class Key, class Value, class KeyOfValue, class Compare>
  850. void rb_tree<Key, Value, KeyOfValue, Compare>::erase (iterator position)
  851. {
  852.     link_type z;
  853.     __initialize(z, link_type(position.node));
  854.     link_type y = z;
  855.     link_type x;
  856.     if (left(y) == NIL)
  857.         x = right(y);
  858.     else
  859.         if (right(y) == NIL)
  860.             x = left(y);
  861.         else
  862.         {
  863.             y = right(y);
  864.             while (left(y) != NIL) y = left(y);
  865.             x = right(y);
  866.         }
  867.     if (y != z)
  868.     {
  869.         //
  870.         // Relink y in place of z.
  871.         //
  872.         parent(left(z)) = y;
  873.         left(y) = left(z);
  874.         if (y != right(z))
  875.         {
  876.             parent(x)        = parent(y); // Possibly x == NIL.
  877.             left(parent(y))  = x;         // Y must be a left child.
  878.             right(y)         = right(z);
  879.             parent(right(z)) = y;
  880.         }
  881.         else
  882.             parent(x) = y;  // Needed in case x == NIL.
  883.         if (root() == z)
  884.             root() = y;
  885.         else if (left(parent(z)) == z)
  886.             left(parent(z)) = y;
  887.         else
  888.             right(parent(z)) = y;
  889.         parent(y) = parent(z);
  890. #ifndef RWSTD_NO_NAMESPACE
  891.         std::swap(color(y), color(z));
  892. #else
  893.         ::swap(color(y), color(z));
  894. #endif
  895.         y = z; // y points to node to be actually deleted.
  896.     }
  897.     else
  898.     {
  899.         //
  900.         // y == z
  901.         //
  902.         parent(x) = parent(y);   // Possibly x == NIL.
  903.         if (root() == z)
  904.             root() = x;
  905.         else
  906.             if (left(parent(z)) == z)
  907.                 left(parent(z)) = x;
  908.             else
  909.                 right(parent(z)) = x;
  910.         if (leftmost() == z)
  911.             if (right(z) == NIL)  // left(z) must be NIL also.
  912.                 leftmost() = parent(z);
  913.                 //
  914.                 // makes leftmost() == header if z == root()
  915.                 //
  916.         else
  917.             leftmost() = minimum(x);
  918.         if (rightmost() == z)
  919.             if (left(z) == NIL) // right(z) must be NIL also.
  920.                 rightmost() = parent(z);
  921.                 //
  922.                 // makes rightmost() == header if z == root().
  923.                 //
  924.         else
  925.             //
  926.             // x == left(z)
  927.             //
  928.             rightmost() = maximum(x);
  929.     }
  930.     if (color(y) != RED)
  931.     {
  932.         while (x != root() && color(x) == BLACK)
  933.             if (x == left(parent(x)))
  934.             {
  935.                 link_type w = right(parent(x));
  936.                 if (color(w) == RED)
  937.                 {
  938.                     color(w)         = BLACK;
  939.                     color(parent(x)) = RED;
  940.                     rotate_left(parent(x));
  941.                     w = right(parent(x));
  942.                 }
  943.                 if (color(left(w)) == BLACK && color(right(w)) == BLACK)
  944.                 {
  945.                     color(w) = RED;
  946.                     x = parent(x);
  947.                 }
  948.                 else
  949.                 {
  950.                     if (color(right(w)) == BLACK)
  951.                     {
  952.                         color(left(w)) = BLACK;
  953.                         color(w)       = RED;
  954.                         rotate_right(w);
  955.                         w = right(parent(x));
  956.                     }
  957.                     color(w) = color(parent(x));
  958.                     color(parent(x)) = BLACK;
  959.                     color(right(w))  = BLACK;
  960.                     rotate_left(parent(x));
  961.                     break;
  962.                 }
  963.             }
  964.             else
  965.             {
  966.                 //
  967.                 // Same as then clause with "right" and "left" exchanged.
  968.                 //
  969.                 link_type w = left(parent(x));
  970.                 if (color(w) == RED)
  971.                 {
  972.                     color(w)         = BLACK;
  973.                     color(parent(x)) = RED;
  974.                     rotate_right(parent(x));
  975.                     w = left(parent(x));
  976.                 }
  977.                 if (color(right(w)) == BLACK && color(left(w)) == BLACK)
  978.                 {
  979.                     color(w) = RED; x = parent(x);
  980.                 }
  981.                 else
  982.                 {
  983.                     if (color(left(w)) == BLACK)
  984.                     {
  985.                         color(right(w)) = BLACK;
  986.                         color(w)        = RED;
  987.                         rotate_left(w);
  988.                         w = left(parent(x));
  989.                     }
  990.                     color(w) = color(parent(x));
  991.                     color(parent(x)) = BLACK;
  992.                     color(left(w))   = BLACK;
  993.                     rotate_right(parent(x));
  994.                     break;
  995.                 }
  996.             }
  997.         color(x) = BLACK;
  998.     }
  999.     destroy(value_allocator.address(value(y)));
  1000.     put_node(y);
  1001.     --node_count;
  1002. }
  1003.  
  1004. template <class Key, class Value, class KeyOfValue, class Compare>
  1005. rb_tree<Key, Value, KeyOfValue, Compare>::size_type
  1006. rb_tree<Key, Value, KeyOfValue, Compare>::erase (const Key& x)
  1007. {
  1008.     pair_iterator_iterator p = equal_range(x);
  1009.     size_type n;
  1010.     __initialize(n, size_type(0));
  1011.     distance(p.first, p.second, n);
  1012.     erase(p.first, p.second);
  1013.     return n;
  1014. }
  1015.  
  1016. template <class Key, class Value, class KeyOfValue, class Compare>
  1017. rb_tree<Key, Value, KeyOfValue, Compare>::link_type
  1018. rb_tree<Key, Value, KeyOfValue, Compare>::__copy (link_type x, link_type p)
  1019. {
  1020.    //
  1021.    // Structural copy.
  1022.    //
  1023.    link_type r = x;
  1024.    while (x != NIL)
  1025.    {
  1026.       link_type y = get_node();
  1027.       if (r == x) r = y;  // Save for return value.
  1028.       construct(value_allocator.address(value(y)), value(x));
  1029.       left(p)   = y;
  1030.       parent(y) = p;
  1031.       color(y)  = color(x);
  1032.       right(y)  = __copy(right(x), y);
  1033.       p         = y;
  1034.       x         = left(x);
  1035.    }
  1036.    left(p) = NIL;
  1037.    return r;
  1038. }
  1039.  
  1040. template <class Key, class Value, class KeyOfValue, class Compare>
  1041. void rb_tree<Key, Value, KeyOfValue, Compare>::__erase (link_type x)
  1042. {
  1043.     //
  1044.     // Erase without rebalancing.
  1045.     //
  1046.     while (x != NIL)
  1047.     {
  1048.        __erase(right(x));
  1049.        link_type y = left(x);
  1050.        destroy(value_allocator.address(value(x)));
  1051.        put_node(x);
  1052.        x = y;
  1053.     }
  1054. }
  1055.  
  1056. template <class Key, class Value, class KeyOfValue, class Compare>
  1057. void rb_tree<Key, Value, KeyOfValue, Compare>::erase (iterator first,
  1058.                                                       iterator locallast)
  1059. {
  1060.     if (first == begin() && locallast == end() && node_count != 0)
  1061.     {
  1062.         __erase(root());
  1063.         leftmost()  = header;
  1064.         root()      = NIL;
  1065.         rightmost() = header;
  1066.         node_count  = 0;
  1067.     } else
  1068.         while (first != locallast) erase(first++);
  1069. }
  1070.  
  1071. template <class Key, class Value, class KeyOfValue, class Compare>
  1072. void rb_tree<Key, Value, KeyOfValue, Compare>::erase (const Key* first,
  1073.                                                       const Key* last)
  1074. {
  1075.     while (first != last) erase(*first++);
  1076. }
  1077.  
  1078. template <class Key, class Value, class KeyOfValue, class Compare>
  1079. rb_tree<Key, Value, KeyOfValue, Compare>::iterator
  1080. rb_tree<Key, Value, KeyOfValue, Compare>::find (const Key& k)
  1081. {
  1082.     link_type y = header;  // Last node that is not less than k.
  1083.     link_type x = root();  // Current node.
  1084.  
  1085.     while (x != NIL)
  1086.     {
  1087.         if (!key_compare(key(x), k))
  1088.             y = x, x = left(x);
  1089.         else
  1090.             x = right(x);
  1091.     }
  1092.     iterator j = iterator(y);
  1093.     return (j == end() || key_compare(k, key(j.node))) ? end() : j;
  1094. }
  1095.  
  1096. template <class Key, class Value, class KeyOfValue, class Compare>
  1097. rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator
  1098. rb_tree<Key, Value, KeyOfValue, Compare>::find (const Key& k) const
  1099. {
  1100.     link_type y = header;  // Last node that is not less than k.
  1101.     link_type x = root();  // Current node.
  1102.  
  1103.     while (x != NIL)
  1104.     {
  1105.         if (!key_compare(key(x), k))
  1106.             y = x, x = left(x);
  1107.         else
  1108.             x = right(x);
  1109.     }
  1110.     const_iterator j = const_iterator(y);
  1111.     return (j == end() || key_compare(k, key(j.node))) ? end() : j;
  1112. }
  1113.  
  1114. template <class Key, class Value, class KeyOfValue, class Compare>
  1115. rb_tree<Key, Value, KeyOfValue, Compare>::size_type
  1116. rb_tree<Key, Value, KeyOfValue, Compare>::count (const Key& k) const
  1117. {
  1118.     pair<const_iterator, const_iterator> p = equal_range(k);
  1119.     size_type n;
  1120.     __initialize(n, size_type(0));
  1121.     distance(p.first, p.second, n);
  1122.     return n;
  1123. }
  1124.  
  1125. template <class Key, class Value, class KeyOfValue, class Compare>
  1126. rb_tree<Key, Value, KeyOfValue, Compare>::iterator
  1127. rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound (const Key& k)
  1128. {
  1129.     link_type y = header;  // Last node that is not less than k.
  1130.     link_type x = root();  // Current node.
  1131.  
  1132.     while (x != NIL)
  1133.     {
  1134.         if (!key_compare(key(x), k))
  1135.             y = x, x = left(x);
  1136.         else
  1137.             x = right(x);
  1138.     }
  1139.  
  1140.     return iterator(y);
  1141. }
  1142.  
  1143. template <class Key, class Value, class KeyOfValue, class Compare>
  1144. rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator
  1145. rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound (const Key& k) const
  1146. {
  1147.     link_type y = header;  // Last node that is not less than k.
  1148.     link_type x = root();  // Current node.
  1149.  
  1150.     while (x != NIL)
  1151.     {
  1152.         if (!key_compare(key(x), k))
  1153.             y = x, x = left(x);
  1154.         else
  1155.             x = right(x);
  1156.     }
  1157.  
  1158.     return const_iterator(y);
  1159. }
  1160.  
  1161. template <class Key, class Value, class KeyOfValue, class Compare>
  1162. rb_tree<Key, Value, KeyOfValue, Compare>::iterator
  1163. rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound (const Key& k)
  1164. {
  1165.     link_type y = header;  // Last node that is greater than k.
  1166.     link_type x = root();  // Current node.
  1167.  
  1168.     while (x != NIL)
  1169.     {
  1170.         if (key_compare(k, key(x)))
  1171.             y = x, x = left(x);
  1172.         else
  1173.             x = right(x);
  1174.     }
  1175.  
  1176.     return iterator(y);
  1177. }
  1178.  
  1179. template <class Key, class Value, class KeyOfValue, class Compare>
  1180. rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator
  1181. rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound (const Key& k) const
  1182. {
  1183.     link_type y = header;  // Last node that is greater than k.
  1184.     link_type x = root();  // Current node.
  1185.  
  1186.     while (x != NIL)
  1187.     {
  1188.         if (key_compare(k, key(x)))
  1189.             y = x, x = left(x);
  1190.         else
  1191.             x = right(x);
  1192.     }
  1193.  
  1194.     return const_iterator(y);
  1195. }
  1196.  
  1197. template <class Key, class Value, class KeyOfValue, class Compare>
  1198. rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_iterator
  1199. rb_tree<Key, Value, KeyOfValue, Compare>::equal_range (const Key& k)
  1200. {
  1201.     pair_iterator_iterator tmp(lower_bound(k), upper_bound(k));
  1202.     return tmp;
  1203. }
  1204.  
  1205. template <class Key, class Value, class KeyOfValue, class Compare>
  1206. rb_tree<Key, Value, KeyOfValue, Compare>::pair_citerator_citerator
  1207. rb_tree<Key, Value, KeyOfValue, Compare>::equal_range (const Key& k) const
  1208. {
  1209.     pair_citerator_citerator tmp(lower_bound(k), upper_bound(k));
  1210.     return tmp;
  1211. }
  1212.  
  1213. template <class Key, class Value, class KeyOfValue, class Compare>
  1214. inline void
  1215. rb_tree<Key, Value, KeyOfValue, Compare>::rotate_left (link_type x)
  1216. {
  1217.     link_type y = right(x);
  1218.     right(x) = left(y);
  1219.     if (left(y) != NIL)
  1220.         parent(left(y)) = x;
  1221.     parent(y) = parent(x);
  1222.     if (x == root())
  1223.         root() = y;
  1224.     else if (x == left(parent(x)))
  1225.         left(parent(x)) = y;
  1226.     else
  1227.         right(parent(x)) = y;
  1228.     left(y) = x;
  1229.     parent(x) = y;
  1230. }
  1231.  
  1232. template <class Key, class Value, class KeyOfValue, class Compare>
  1233. inline void
  1234. rb_tree<Key, Value, KeyOfValue, Compare>::rotate_right (link_type x)
  1235. {
  1236.     link_type y = left(x);
  1237.     left(x) = right(y);
  1238.     if (right(y) != NIL)
  1239.         parent(right(y)) = x;
  1240.     parent(y) = parent(x);
  1241.     if (x == root())
  1242.         root() = y;
  1243.     else if (x == right(parent(x)))
  1244.         right(parent(x)) = y;
  1245.     else
  1246.         left(parent(x)) = y;
  1247.     right(y) = x;
  1248.     parent(x) = y;
  1249. }
  1250.  
  1251. #ifndef RWSTD_NO_NAMESPACE
  1252. }
  1253. #endif
  1254.  
  1255. #endif
  1256.  
  1257.